def prefix_sum_array2(grid):
    '''
        二维数组前缀和
    '''
    m, n = len(grid), len(grid[0])
    prefix_sum = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                prefix_sum[i][j] = grid[i][j]
            elif i == 0:
                prefix_sum[i][j] = grid[i][j] + prefix_sum[i][j - 1]
            elif j == 0:
                prefix_sum[i][j] = grid[i][j] + prefix_sum[i - 1][j]
            else:
                prefix_sum[i][j] = grid[i][j] + prefix_sum[
                    i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
    return prefix_sum


def pre_sum_array2_area_tot(grid, left_top, right_bottom, out_of_range):
    m, n = len(grid), len(grid[0])
    tx, ty, bx, by = left_top[0], left_top[1], right_bottom[0], right_bottom[1]
    if tx < 0 or ty < 0 or bx >= m or by >= n:
        return out_of_range
    if tx == 0 and ty == 0:
        return grid[bx][by]
    if tx == 0:
        return grid[bx][by] - grid[bx][ty - 1]
    if ty == 0:
        return grid[bx][by] - grid[tx - 1][by]
    return grid[bx][by] - grid[bx][ty - 1] - grid[tx - 1][by] + grid[tx -
                                                                     1][ty - 1]


grid = [[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

pre_sums = prefix_sum_array2(grid)

print(pre_sum_array2_area_tot(pre_sums,(0,0),(3,3),100))


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right